package com.tgy.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: tgy
 * @Date: 12/1/20 10:20 AM
 *
 * https://leetcode-cn.com/problems/sliding-window-maximum/
 */
public class _239_滑动窗口最大值_01 {

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || k <= 0 || nums.length < k) {

            return new int[0];
        }

        if (k == 1) {

            return nums;
        }

        int preIndex = max(nums,0,k - 1);
        int[] ret = new int[nums.length - k + 1];

        ret[0] = nums[preIndex];

        for (int i = 1; i < ret.length; i++) {

            int right = i + k - 1;
            if (preIndex >= i) {

                if (nums[preIndex] < nums[right]) {

                    preIndex = right;
                }
            }else {
                if (nums[preIndex] <= nums[right]) {

                    preIndex = right;
                }else {

                    preIndex = max(nums,i,right);
                }
            }

            ret[i] = nums[preIndex];
        }

        return ret;
    }

    private int max(int[] nums, int start,int end) {

        int max = nums[start];
        int index = start;

        for (int i = start + 1; i <= end; i++) {

            if (max < nums[i]) {

                max = nums[i];
                index = i;
            }
        }

        return index;
    }
}
